/**
 * Created with IntelliJ IDEA
 * Description:
 * User: lenovo
 * Date: 2023 -04 -25
 * Time: 10:28
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Work {
    //根据后序遍历和中序遍历创建二叉树
    public int postIndex=0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {

        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }
    public TreeNode buildTreeChild(int[] inorder, int[] postorder,int inBegin,int inEnd){
        if(inBegin>inEnd){
            return null;
        }
            TreeNode root=new TreeNode(postorder[postIndex]);
            int rootIndex=findIndex(inorder,inBegin,inEnd,postorder[postIndex]);
            postIndex--;
        root.right=buildTreeChild(inorder,postorder,rootIndex+1,inEnd);
            root.left=buildTreeChild(inorder,postorder,inBegin,rootIndex-1);

            return  root;
    }
    public int findIndex(int[] inorder,int inBegin,int inEnd,int key){
        for (int i = inBegin; i <=inEnd ; i++) {
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }
    //根据前序遍历，和中序遍历创建二叉树
    /*public int preindex=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend){
        if(inbegin>inend){
            return null;
        }
        TreeNode root=new TreeNode(preorder[preindex]);
        int rootIndex=findIndex(inorder,inbegin,inend,preorder[preindex]);
        preindex++;
        root.left=buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right=buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    public int findIndex(int[] inorder,int inbegin,int inend,int key){
        for (int i = inbegin; i < =inend; i++) {
            if(inorder[i]==key)
                return i;
        }
        return -1;
    }*/
}
